/**
 * 暴力法
 */
function subarraySum(nums: number[], k: number): number {
  let count = 0
  for (let i = 0; i < nums.length; i++) {
      if (nums[i] === k) {
          count++
      }
      let sum = nums[i]
      for (let j = i + 1; j < nums.length; j++) {
          sum += nums[j]
          if (sum === k) {
              count++
          }
      }
  }
  return count
}

/**
 * 前缀和 配合哈希表
 * pre[j] - pre[i] === k
 * => 找到所有 的 pre[?] 为 pre[j] - k
 * 哈希表记录不同前缀和的数量 
 * mp[所求的和] 的数量
 */
function subarraySum2(nums: number[], k: number): number {
  const mp = new Map()
  mp.set(0, 1); // mp[0] = 1
  let count = 0
  let pre = 0
  for (const x of nums) {
      pre += x;
      if (mp.has(pre - k)) {
          count += mp.get(pre - k) // 这个前缀和是满足条件的，所以记录的都符合
      }
      if (mp.has(pre)) {
          mp.set(pre, mp.get(pre) + 1)
      } else {
          mp.set(pre, 1)
      }
  }
  return count
}